import java.util.Random;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
    public void sortColors(int[] nums) {
        int l=0,r=nums.length-1;
        for(int i=0;i<=r;){
            if(nums[i]==0){
                swap(nums,l,i);
                l++;
                i++;
            }
            else if(nums[i]==2){
                swap(nums,r,i);
                r--;
            }
            else i++;
        }
    }
    public void swap(int[] nums,int n,int i){
        int a=nums[n];
        nums[n]=nums[i];
        nums[i]=a;
    }
    public int[] sortArray(int[] nums) {
        qsort(nums,0,nums.length-1);
        return nums;
    }
    public void qsort(int[] nums,int l,int r){
        if(l>=r) return;
        int key=nums[new Random().nextInt(r-l+1)+l];
        int left=l-1,right=r+1,i=l;
        while(i<right){
            if(nums[i]<key) swap(nums,++left,i++);
            else if(nums[i]>key) swap(nums,--right,i);
            else i++;
        }
        qsort(nums,l,left);
        qsort(nums,right,r);
    }
    public int findKthLargest(int[] nums, int k) {
        return qsort2(nums,0,nums.length-1,k);
    }
    public int qsort2(int[] nums,int l,int r,int k){
        if(l==r) return nums[l];
        int key=nums[new Random().nextInt(r-l+1)+l];
        int left=l-1,right=r+1,i=l;
        while(i<right){
            if(nums[i]<key) swap(nums,++left,i++);
            else if(nums[i]>key) swap(nums,--right,i);
            else i++;
        }
        if(r-right+1>=k) return qsort2(nums,right,r,k);
        else if(r-left>=k) return key;
        else return qsort2(nums,l,left,k-r+left);
    }
    public int[] smallestK(int[] arr, int k) {
        int[] ret=new int[k];
        qsort3(arr,0,arr.length-1,k);
        for(int i=0;i<ret.length;i++){
            ret[i]=arr[i];
        }
        return ret;
    }
    public void qsort3(int[] arr,int l,int r,int k){
        if(l>=r) return;
        int key=arr[new Random().nextInt(r-l+1)+l],left=l-1,right=r+1,i=l;
        while(i<right){
            if(arr[i]<key) swap(arr,++left,i++);
            else if(arr[i]>key) swap(arr,--right,i);
            else i++;
        }
        int a=left-l+1,b=right-l,c=r-right+1;
        if(a>k) qsort3(arr,l,left,k);
        else if(b>=k) return;
        else qsort3(arr,right,r,k-b);
    }
    int[] tmp;
    public int[] sortArray2(int[] nums) {
        tmp=new int[nums.length];
        mergeSort(nums,0,nums.length-1);
        return nums;
    }
    public void mergeSort(int[] nums,int left,int right){
        if(left>=right) return;
        int mid=(left+right)/2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        int cur1=left,cur2=mid+1,i=0;
        while(cur1<=mid&&cur2<=right){
            tmp[i++]=nums[cur1]<nums[cur2]?nums[cur1++]:nums[cur2++];
        }
        while(cur1<=mid) tmp[i++]=nums[cur1++];
        while(cur2<=right) tmp[i++]=nums[cur2++];
        for(int j=left;j<=right;j++){
            nums[j]=tmp[j-left];
        }
    }
}